package leetcode100;

// TODO 双指针 [经典] 【-】 颜色分类
// TODO https://leetcode.cn/problems/sort-colors/solution/shuang-zhi-zhen-fang-fa-goyu-yan-shi-xia-9u2z/

public class lc100_0075 {

    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = 0, right = nums.length-1; // / left: 红色  right: 蓝色

        for (int i=0; i<=right;) {
            // 如果扫描到 0, 则其左边已经全是 0 和 1 了, 所以交换之后 i 位置一定是 1, 可以直接 i++
            if (nums[i] == 0) {
                int tmp = nums[left];
                nums[left] = nums[i];
                nums[i] = tmp;
                left++;
                i++;
            } else if (nums[i] == 2) {
                int tmp = nums[right];
                nums[right] = nums[i];
                nums[i] = tmp;
                right--;
            } else {
                i++;
            }
        }
    }

}
